class Solution {
public:
    unordered_map<int, int> ma;
    pair<int, bool> dp[15][2][1200][2];
    int countSpecialNumbers(int n) {
        ma[1] = 0;
        int temp = 1;
        for (int i = 1; i <= 9; i++)
        {
            temp *= 2;
            ma[temp] = i;
        }
        string s = to_string(n);
        return dfs(0, 0, (1 << 10) - 1, s, 0);
    }
    int dfs(int pos, int free, int t, string& s, int pre)
    {
        if (pos >= s.size()) return pre;
        if (dp[pos][free][t][pre].second) return dp[pos][free][t][pre].first;
        int ans = 0;
        if (!pre)
        {
            ans += dfs(pos + 1, 1, t, s, pre);
            if (free)
            {
                for (int i = t; i; i -= i & (-i))
                {
                    if (!ma[i & (-i)]) continue;
                    ans += dfs(pos + 1, free, t - (i & (-i)), s, 1);
                }
            }
            else
            {
                for (int i = t; i; i -= i & (-i))
                {
                    if (!ma[i & (-i)]) continue;
                    if (ma[i & (-i)] + '0' <= s[pos])
                    {
                        if (ma[i & (-i)] + '0' < s[pos])
                        {
                            ans += dfs(pos + 1, 1, t - (i & (-i)), s, 1);
                        }
                        else ans += dfs(pos + 1, 0, t - (i & (-i)), s, 1);
                    }
                }
            }
        }
        else
        {
            if (free)
            {
                for (int i = t; i; i -= i & (-i))
                {
                    ans += dfs(pos + 1, free, t - (i & (-i)), s, 1);
                }
            }
            else
            {
                for (int i = t; i; i -= i & (-i))
                {
                    if (ma[i & (-i)] + '0' <= s[pos])
                    {
                        if (ma[i & (-i)] + '0' < s[pos])
                        {
                            ans += dfs(pos + 1, 1, t - (i & (-i)), s, 1);
                        }
                        else ans += dfs(pos + 1, 0, t - (i & (-i)), s, 1);
                    }
                }
            }
        }
        dp[pos][free][t][pre].second = 1;
        return dp[pos][free][t][pre].first = ans;
    }
};